Intersection of Two Line Segments
Two line segments will be represented by their endpoints and given in vector notation. The intersection of line segments is not so easy as it might seem. For example, in the system that will be shown, one of the segments will be vertical, making the slope unattainable. Other things could also go poorly. Lines intersect, but line segments might not. We would like to know if they do not intersect. One way is to graph them and look. But if the work is being done inside a computer, there needs to be a way to tell the computer if they intersect or not.
Example: Given a line segment with
endpoints $P=\left[\begin{array}{c}
2\\
0
\end{array}\right] \:\:Q=\left[\begin{array}{c}
2\\
5
\end{array}\right]$,
Does that segment intersect with another segment given by points $H=\left[\begin{array}{c}
3\\
2
\end{array}\right] \:K=\left[\begin{array}{c}
5\\
1
\end{array}\right]$ ?
Answer: Let P be a starting point on the first segment and identify a direction vector as $\mathbf{b}=\left[Q-P\right]$, then for the scalar $t$ $(0\leq t\leq1)$, {Aside: When $t=0$, $(x,y)=P$ and when $t=1$, $(x,y)=Q$. That is why $t$ between $0$ and $1$ defines the line segment. $t$ with any other values just puts a point on the line rather than the line segment. every point on the segment can be identified by the equation $(x,y)=\mathbf{P}+t\cdot\mathbf{b}$. Equation $\eqref{EQ 1}$ expands this $P\rightarrow Q$ segment. $$\left(\begin{array}{c} x\\ y \end{array}\right)=\mathbf{P}+t\cdot\mathbf{b}=\left(\begin{array}{c} 2\\ 0 \end{array}\right)+t\left(\left(\begin{array}{c} 2\\ 5 \end{array}\right)-\left(\begin{array}{c} 2\\ 0 \end{array}\right)\right)=\left(\begin{array}{c} 2\\ 0 \end{array}\right)+t\left(\begin{array}{c} 0\\ 5 \end{array}\right)\quad0\le t\le1 \tag{EQ 1} \label{EQ 1}$$ For the second line segment, $H\rightarrow K$, by analogy if I have scalar $u (0\leq u\leq1)$, then a second equation exists, $(x,y)=\mathbf{H}+u\cdot\mathbf{b_{1}}$, where $\mathbf{b_{1}}=\left[K-H\right]$. Equation $\eqref{EQ 2}$ shows this equation with the number values inserted. $$\left(\begin{array}{c} x\\ y \end{array}\right)=\mathbf{H}+u\cdot\mathbf{b_{1}}=\left(\begin{array}{c} 3\\ 2 \end{array}\right)+u\left(\left(\begin{array}{c} 5\\ 1 \end{array}\right)-\left(\begin{array}{c} 3\\ 2 \end{array}\right)\right)=\left(\begin{array}{c} 3\\ 2 \end{array}\right)+u\left(\begin{array}{c} 2\\ -1 \end{array}\right)\quad0\le u\le1 \tag{EQ 2} \label{EQ 2}$$ Equations $\eqref{EQ 1}$ and $\eqref{EQ 2}$ represent four equations in the unknowns $\{x,y,t,u\}$. We will write them out. $$x=2+t\cdot0$$ $$y=0+t\cdot5$$ $$x=3+u\cdot2$$ $$y=2+u\cdot(-1)$$ These solve to $(x,y,t,u)=(2,\,5/2,\,1/2,\,-1/2)$. Because $u$ is not between $0$ and $1$, these segments do not intersect. The Listing below shows code for this problem which could be easily generalized and the left figure panel shows these line seqments on a graph.
Answer: Let P be a starting point on the first segment and identify a direction vector as $\mathbf{b}=\left[Q-P\right]$, then for the scalar $t$ $(0\leq t\leq1)$, {Aside: When $t=0$, $(x,y)=P$ and when $t=1$, $(x,y)=Q$. That is why $t$ between $0$ and $1$ defines the line segment. $t$ with any other values just puts a point on the line rather than the line segment. every point on the segment can be identified by the equation $(x,y)=\mathbf{P}+t\cdot\mathbf{b}$. Equation $\eqref{EQ 1}$ expands this $P\rightarrow Q$ segment. $$\left(\begin{array}{c} x\\ y \end{array}\right)=\mathbf{P}+t\cdot\mathbf{b}=\left(\begin{array}{c} 2\\ 0 \end{array}\right)+t\left(\left(\begin{array}{c} 2\\ 5 \end{array}\right)-\left(\begin{array}{c} 2\\ 0 \end{array}\right)\right)=\left(\begin{array}{c} 2\\ 0 \end{array}\right)+t\left(\begin{array}{c} 0\\ 5 \end{array}\right)\quad0\le t\le1 \tag{EQ 1} \label{EQ 1}$$ For the second line segment, $H\rightarrow K$, by analogy if I have scalar $u (0\leq u\leq1)$, then a second equation exists, $(x,y)=\mathbf{H}+u\cdot\mathbf{b_{1}}$, where $\mathbf{b_{1}}=\left[K-H\right]$. Equation $\eqref{EQ 2}$ shows this equation with the number values inserted. $$\left(\begin{array}{c} x\\ y \end{array}\right)=\mathbf{H}+u\cdot\mathbf{b_{1}}=\left(\begin{array}{c} 3\\ 2 \end{array}\right)+u\left(\left(\begin{array}{c} 5\\ 1 \end{array}\right)-\left(\begin{array}{c} 3\\ 2 \end{array}\right)\right)=\left(\begin{array}{c} 3\\ 2 \end{array}\right)+u\left(\begin{array}{c} 2\\ -1 \end{array}\right)\quad0\le u\le1 \tag{EQ 2} \label{EQ 2}$$ Equations $\eqref{EQ 1}$ and $\eqref{EQ 2}$ represent four equations in the unknowns $\{x,y,t,u\}$. We will write them out. $$x=2+t\cdot0$$ $$y=0+t\cdot5$$ $$x=3+u\cdot2$$ $$y=2+u\cdot(-1)$$ These solve to $(x,y,t,u)=(2,\,5/2,\,1/2,\,-1/2)$. Because $u$ is not between $0$ and $1$, these segments do not intersect. The Listing below shows code for this problem which could be easily generalized and the left figure panel shows these line seqments on a graph.
This is how to solve a vector equation of a line
segment using SAGE solve.
r = a + t*b
s = a1 + u*b1 line segment equations.
The intersection is where r = s
let a=P; b=Q-P let a1 = H; b1=K-H.
#-----------------------------------------------
P=vector([2,0]);Q=vector([2,5])
H=vector([3,2]);K=vector([5,1])
a=P;b=Q-P
a1=H;b1=K-H
var('t u')
r=a+t*b
s=a1+u*b1
equ1=r[0]==s[0]
equ2=r[1]==s[1]
show(equ1)
show(equ2)
pc=solve([equ1,equ2],(t,u),solution_dict=True)
cross=a+t*b
print pc
print "Line Intersection Point = ",cross.subs(sol)
#------------- OUTPUT -------------------
[{t: 1/2, u: -1/2}]
Line Intersection Point = (2, 5/2)
segment using SAGE solve.
r = a + t*b
s = a1 + u*b1 line segment equations.
The intersection is where r = s
let a=P; b=Q-P let a1 = H; b1=K-H.
#-----------------------------------------------
P=vector([2,0]);Q=vector([2,5])
H=vector([3,2]);K=vector([5,1])
a=P;b=Q-P
a1=H;b1=K-H
var('t u')
r=a+t*b
s=a1+u*b1
equ1=r[0]==s[0]
equ2=r[1]==s[1]
show(equ1)
show(equ2)
pc=solve([equ1,equ2],(t,u),solution_dict=True)
cross=a+t*b
print pc
print "Line Intersection Point = ",cross.subs(sol)
#------------- OUTPUT -------------------
[{t: 1/2, u: -1/2}]
Line Intersection Point = (2, 5/2)
